package Offer.offer2019;

/**
 * 二叉搜索树的后序遍历序列
 * @author: leiwenkang
 * @date: 2019/5/15
 * @time: 19:49
 */
public class Offer24 {
    public static void main(String[] args) {
        Offer24 offer = new Offer24();
        int[] array = {5, 7, 6, 9, 11, 10, 8};
        System.out.println(offer.isBST(array));
    }

    public boolean isBST(int[] array) {
        if (array == null || array.length == 0) {
            return false;
        }
        return isBST(array, 0, array.length - 1);
    }

    public boolean isBST(int[] array, int start, int end) {
        //终止条件，一个节点时，肯定是二叉搜索时，直接返回true
        if (start >= end) {
            return true;
        }
        //根据后序遍历规则，数组的最后一个元素，即为头结点
        int headValue = array[end];

        //遍历数组 由于是二叉搜索树，数组前面小于头结点的值，是树的左子树，大于头结点的值，是树的右子树
        int i;
        for (i = start; i < end; i++) {
            if (array[i] > headValue) {
                break;
            }
        }
        //找到第一个大于头结点的值后，将数组一分为二，理应后面的元素应均大于头结点,若有元素小于头结点，则说明该树不是二叉搜索树
        for (int j = i; j < end; j++) {
            if (array[j] < headValue) {
                return false;
            }
        }
        //将数组顺利一分为二后，判断左右子树，是否均是二叉搜索树
        return isBST(array, start, i - 1) && isBST(array, i, end - 1);
    }

}
